package breakfastNumber;

import java.util.Arrays;

public class Solution {
    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        // 排序 + 二分
//        int MOD = 1000000007;
//        Arrays.sort(drinks);
//        long ans = 0;
//        for (int stap: staple) {
//            ans = (ans+binarySearch(drinks,x-stap))%MOD;
//        }
//        return (int) ans;

        // 排序 + 双指针
        Arrays.sort(staple);
        Arrays.sort(drinks);
        int ans = 0,MOD = 1000000007;
        int i = 0,j = drinks.length-1;
        while (i<staple.length&&j>=0) {
            if(staple[i] + drinks[j]<=x) {
                ans = ( ans + j + 1)%MOD;
                i++;
            }else {
                j--;
            }
        }
        return ans;
    }

    // 找到所有小于等于target的数字
//    private int binarySearch(int[] drinks,int target) {
//        int l = 0,r = drinks.length-1;
//        while (l<=r) {
//            int mid = l + (r-l)/2;
//            if(drinks[mid]<=target) {
//                l = mid+1;
//            }else {
//                r = mid-1;
//            }
//        }
//        return l;
//    }
}
